/***************************************************************************************************
  *Copyright(C),2010-2016,Sumscope
  *FileName	:  pinyin_search_engine.cpp
  *Author	:  scofined.qi
  *Version	:  1.0
  *Date		:  2017/06/04
  *Desc		:  //用于主要说明此程序文件完成的主要功能
  *Relation :  
  *Others	:  //其他内容说明
  *Function :  //主要函数列表，每条记录应包含函数名及功能简要说明
  *History	:  //修改历史记录列表，每条修改记录应包含修改日期、修改者及修改内容简介
***************************************************************************************************/
#include "pinyin_search_engine.h"
#include "pinyin_search_buffer.h"
#include "../BaseString.h"
#include "../pinyin.h"
#include "../md5.h"
#include <algorithm>
#include <unordered_map>
#include <core/Utility.h>
#include <core/FileSys.h>
#include <core/container/hash_prime.h>

#ifdef WIN32
#include <process.h>
#endif

#ifndef BASSERTS
#define BASSERTS //
#endif
#ifndef BASSERT
#define BASSERT //
#endif
#ifndef BLOGERR
#define BLOGERR //
#endif
#ifndef BLOGINFO
#define BLOGINFO //
#endif
#ifndef BLOGDEBUG
#define BLOGDEBUG //
#endif
#ifndef BVIEW
#define BVIEW //
#endif
#ifndef MEM_METRIC
#define MEM_METRIC //
#endif
#ifndef BS_METRICS
#define BS_METRICS //
#endif

typedef qb::base::StringPage StringPage;
//typedef qb::base::SLogFileMapping SLogFileMapping;
namespace qb{
	namespace base{
#define ROUND4(num) ((num%4==0)?num:((num/4+1)*4))
#define ROUND_ALIGN(NUM, SIZE) ((NUM%SIZE==0)?NUM:((NUM/SIZE+1)*SIZE))
		namespace internal{
			extern const int kReverseKeyLen2 = 2;
			extern const int kKeyLen = 3;
			static_assert(kReverseKeyLen2>0 && kReverseKeyLen2 < kKeyLen, "kReverseKeyLen2 & kKeyLen has invalid values");
			static bool IsTinyKeyLogEnable(){
				static bool init = false;
				static bool enable = true;
                if (!init){ init = true; enable = false; }
				return enable;
			}
			/*
				用于开启另外的实现分支
				有三种实现分支:
				1.使用InverseSetOld作为内存中的map
				2.使用InverseSetNew作为内存中的map,基于vector,有序数组,二分查找
				3.使用映射文件IndexIdFile作为内存中的map的分配器,基于vector,有序数组,
					二分查找

				三种实现分支效果如下:
				1.InverseSetOld:	加载过程快,内存占用极高,即使BuildIndex中将其全部删
									除替换,内存依旧被占用(原因暂时不明)
				2.InverseSetNew:	加载速度快,内存占用是InverseSetOld的(测量值)一半,
									删除后完全清空,无隐含内存占用(InverseSetOld出了测量
									值外,还有隐含内存占用)
				3.IndexIdFile:		无基本内存占用,但是加载过程慢,高达24s

				此函数返回true表示使用IndexIdFile分支,默认是false,选择InverseSetNew分支
			*/
			namespace{
                bool IsStartWith(const wchar_t* str, const wchar_t* text, int len)
				{
					// 不使用memcpy是避免使用strlen
					const wchar_t* tend = text + len;
					while (*str != 0 && text < tend)
					{
						if (*str++ != *text++)return false;
					}
					return len > 0 && text >= tend;
				}
				class ExistKeyCheck :public WideString{
				public:
					ExistKeyCheck(const wstring& str) :WideString(str.c_str(), str.size()){}
					bool FindExist(const wchar_t* str, int stop)
					{
						if (stop<0 ||stop >= size())
							return false;
						wchar_t old = at(stop);
						at(stop) = 0;
						bool exist = wcsstr(c_str(), str) != NULL;
						at(stop) = old;
						return exist;
					}
				};


				// 将内部id单独打印到一个文件中
            /*	class IdLogger{
					int					m_index;
                    SLogFileMapping		m_file;
					char*				m_buffer;
					int					m_size;
					int					m_capcity;
				public:
					IdLogger() :m_capcity(1024), m_size(0), m_index(0), m_buffer(nullptr)
					{
						SYSTEMTIME st; GetLocalTime(&st);
						char fname[MAX_PATH] = { 0 };
						FMTBUF(fname, ".\\log\\searchid_%04d_%02d_%02d_%06d_%08d.log",
							st.wYear, st.wMonth, st.wDay, GetCurrentProcessId(), GetTickCount());
						int fid = 0;
						m_file.Initialize(fname, fid);
						m_buffer = new char[m_capcity];
						memset(m_buffer, 0, m_capcity);
					}
					~IdLogger()
					{
						if (m_buffer)delete[] m_buffer;
					}
					void Flush()
					{
						if (m_size > 0 && m_buffer)
						{
							m_file.Append(m_buffer, m_size);
						}
						m_size = 0;
					}
					template<class IDVec>
                    void AppendId(const std::wstring& key, const IDVec& ids, const char* type)
					{
						AddIndex(); AddKey(key); AddType(type);
						AddCount(ids.size());
						AddBuffer("id=",3);
						if (ids.size() > 0)
						{
							for (IDVec::const_iterator it = ids.cbegin(); it != ids.cend(); ++it)
							{
								char buf[64] = { 0 };
								int len = FMTBUF(buf, "%d,", it->first);
								AddBuffer(buf, len);
							}
						}
						AddBuffer("\n\n",2);
						Flush();
					}
					void AddGroupLine(){
						AddBuffer("===================================================================================================\n");
					}
					void AddStart(const wstring& key)
					{
						char buf[1024] = { 0 };
						int len = FMTBUF(buf, "start=%s\n", W2G(key.c_str()).c_str());
						AddGroupLine();
						AddBuffer(buf, len);
					}
					void AddIdCode(const char* str, int len)
					{
						AddBuffer(str, len);
					}
					static IdLogger& Get(){
						static IdLogger ilog;
						return ilog;
					}
				protected:
					void AddIndex()
					{
						char buf[64] = { 0 };
						int len=FMTBUF(buf, "index=%d\n",m_index++);
						AddBuffer(buf,len);
					}
					void AddKey(const wstring& key)
					{
						char buf[128] = { 0 };
						int len = FMTBUF(buf, "key=%s\n",W2G(key.c_str()).c_str());
						AddBuffer(buf, len);
					}
					void AddType(const char* type)
					{
						char buf[128] = { 0 };
						int len = FMTBUF(buf, "type=%s\n", type);
						AddBuffer(buf, len);
					}
					void AddCount(int count)
					{
						char buf[64] = { 0 };
						int len = FMTBUF(buf, "count=%d\n",count);
						AddBuffer(buf, len);
					}
				public:
					void AddBuffer(const char* buf,int len=-1)
					{
						if (buf == nullptr)return;
						len = len <= 0 ? strlen(buf) : len;
						if (m_buffer == nullptr || m_size + len >= m_capcity)
						{
							int expect = m_size + len + 1;
							int capcity = m_capcity + m_capcity / 2;
							capcity = capcity < expect ? expect : capcity;
							char* newbuf = new char[capcity];
							memset(newbuf, 0, capcity);
							if (m_buffer)
							{
								memcpy(newbuf, m_buffer, m_size);
								delete[] m_buffer;
							}
							m_buffer = newbuf;
							m_capcity = capcity;
						}
						memcpy(m_buffer + m_size, buf, len);
						m_size += len;
					}
				};
				void WriteIdLog(const wstring& key, const IndexIdVec& ids,const char* type)
				{
					IdLogger::Get().AppendId(key, ids,type);
				}
				void WriteIdLog(const wstring& key, InverseSet*	memory_set, const char* type)
				{
					if (memory_set)
						IdLogger::Get().AppendId(key,*memory_set,type);
                }*/



				/*
				[内存优化][scofined.qi]
				倒排索引键值预估表

				为什么需要:
				建立倒排索引时,对于一个三字符键,到底有多少个债券与之相关,是很困难的.
				如果有个表,预估每个三字键大概有多少个债券与之相关,那么下一次建立倒排
				索引的时候,分配债券索引数组,就能减少扩张次数,进而减少建立倒排索引的时间

				该怎么做:
				每次建立完倒排索引之后,将这些信息保存到本地的一个文件
				即:"./data/BondSearchPredict.bin"
				每次启动的时候,从此文件中读取每个三字符键的债券索引数组的长度
				建立倒排索引创建InverseSet对象后,立即根据此长度,来对
				InverseSetNew2对象进行准确扩容,参见PredictCount

				模式说明:
				为了对比和更好的性能,支持三种模式,kPredictMode
				kPredictModeNone表示不引入倒排索引键值预估表
				kPredictModeArray和kPredictModeSlot分别表示该文件的
				两种格式,对比看哪种格式最终性能更好速度更快	
				最终测试,kPredictModeArray模式效果最好

				改进:m_predictmap使用std::map<InverseKey, int>
				该对象也会使用大量内存,导致内存碎片,而且是临时对象,
				建立倒排索引阶段后就会清空,不再使用
				后续可以使用单个内存堆,以及更好的容器来优化				
				*/
				class InverseKeyHash{
				public:
					size_t operator()(const InverseKey& x) const {
						return x.GetHash();
					}
				};
				class IntHash{
				public:
					size_t operator()(const unsigned int& x) const { return x; }
				};
				typedef CStackHashMap<InverseKey, bool, 128, 256, InverseKeyHash> VisitKeyMap;
				typedef CStackHashMap<unsigned int, bool, 128, 256, IntHash> VisitCodeMap;
				class KeyStat : public std::map<int, std::set<InverseKey>>{
					typedef std::set<InverseKey> KeySet;
					typedef std::map<InverseKey, int> PredictMap;
					typedef SpellSearchImpl::kPredictMode kPredictMode;
					enum{ 
						Magic = 0xABFE,				// 第一种文件格式
						MagicKeyCapcity = 0xBACF,	//第二种文件格式,即KeyCapcity数组
					};
					struct Head{
						unsigned int magic;		// 固定值
						MD5::tMD5	 md5;		// 对KeyStatItem数组以及后续全部InverseKey3数组的md5值
						int			 count;		// KeyStatItem数组有多少个
						int			 kcount;	// InverseKey的个数
						int			 fsize;		// 该文件总大小是多少
						int			 isize;		// KeyStatItem的大小
						int			 ksize;		// InverseKey的大小
					};
					struct KeyStatItem{
						int			capcity;	// 对应KeyStat的key值
						int			index;		// 对应InverseKey3数组的索引
						int			count;		// InverseKey3数组中从index开始的个数
					};
					struct KeyCapcity{			// 第二种文件格式
						InverseKey	key;
						int			capcity;
					};
					BaseString		m_path;
					BaseString		m_fname;
					vector<KeyCapcity>	m_predict;
					bool			m_array_type;	// 只影响保存
					int				m_capcity;
				public:
					KeyStat(bool arrayType,int cap=4096) :m_array_type(arrayType),
						m_capcity(cap)
					{
						m_path = "./data/";
						m_fname = "./data/BondSearchPredict.bin";
					}
					void add(const InverseKey& key, int size)
					{
						if (m_array_type)
						{
							if (m_predict.empty())
								m_predict.reserve(m_capcity);
							if (size > 2)
								m_predict.emplace_back(KeyCapcity{ key, size });
							return;
						}
						int sizeKey = getSizeKey(size);
						auto it = this->find(sizeKey);
						if (it == this->end())
						{
							KeySet kset; kset.insert(key);
							this->emplace(sizeKey, kset);
						}
						else
							it->second.insert(key);
					}
					int getSizeKey(int size)const
					{
						const int maxbase = 32;
						int base = 1;
						while (base < size && base <= maxbase)
						{
							base = base << 1;
						}
						if (base < size)
							base = ((size / maxbase) + 1)*maxbase;
						return base;
					}
					bool save_array()
					{
						int totalSize = sizeof(Head) + m_predict.size()*sizeof(KeyCapcity);
						char* ptr = new char[totalSize];
						if (ptr == nullptr)
						{
							BLOGERR("[MEMORY][PREDICT]alloc for KeyStat failed,size:%d", totalSize);
							return false;
						}
						int index = 0;
						Head* phead = (Head*)ptr;
						KeyCapcity* items = (KeyCapcity*)(ptr + sizeof(Head));
						for (auto it = m_predict.begin(); it != m_predict.end(); ++it, ++index)
						{
							const KeyCapcity& val = *it;
							int cap = val.capcity;
							int gap = cap < 16 ? 2 : (cap < 32 ? 4 : 32);
							items[index].key = val.key;
							items[index].capcity = ROUND_ALIGN(cap, gap);
						}
						if (MD5::FromString((const char*)items, totalSize - sizeof(Head), phead->md5, sizeof(phead->md5)))
						{
							phead->magic = MagicKeyCapcity;
							phead->count = m_predict.size();
							phead->fsize = totalSize;
							phead->kcount = m_predict.size();
							phead->isize = sizeof(KeyCapcity);
							phead->ksize = sizeof(InverseKey);
                            FileSys::instance()->makePathExist(m_path.c_str());
#ifdef WIN32
                            DeleteFileA(m_fname.c_str());
#else
                            remove(m_fname.c_str());
#endif
                            bool suc = StringUtil::SaveFileContent(ptr, totalSize, G2W(m_fname));
							BLOGINFO("[MEMORY][PREDICT]save KeyStat %s!",suc?"succesfully":"failed");
						}else{
							BLOGERR("[MEMORY][PREDICT]make md5 for KeyStat failed");
						}
						delete[] ptr;
						return true;
					}
					bool save()
					{
						if (m_array_type)
							return save_array();
						int totalKeyCount = 0;
						for (auto it = this->begin(); it != this->end(); ++it)
						{
							KeySet& kset = it->second;
							totalKeyCount += kset.size();
						}
						int itemCount = this->size();
						int fixedSize = sizeof(Head) + itemCount*sizeof(KeyStatItem);
						int totalSize = fixedSize + totalKeyCount*sizeof(InverseKey);
						char* ptr = new char[totalSize];
						if (ptr == nullptr)
						{
							BLOGERR("[MEMORY][PREDICT]alloc for KeyStat failed,size:%d", totalSize);
							return false;
						}
						Head* phead = (Head*)ptr;
						KeyStatItem* items = (KeyStatItem*)(ptr + sizeof(Head));
						InverseKey* keys = (InverseKey*)(ptr + fixedSize);
						int index = 0, keyIndex = 0;
						for (auto it = this->begin(); it != this->end(); ++it, ++index)
						{
							KeySet& kset = it->second;
							items[index].capcity = it->first;
							items[index].count = kset.size();
							items[index].index = keyIndex;
							for (auto kit = kset.begin(); kit != kset.end(); ++kit)
							{
								keys[keyIndex++] = *kit;
							}
						}
						phead->magic = Magic;
						if (MD5::FromString((const char*)items, totalSize - sizeof(Head), phead->md5, sizeof(phead->md5)))
						{
							phead->fsize = totalSize;
							phead->count = itemCount;
							phead->kcount = totalKeyCount;
							phead->isize = sizeof(KeyStatItem);
							phead->ksize = sizeof(InverseKey);
                            FileSys::instance()->makePathExist(m_path.c_str());
#ifdef WIN32
                            DeleteFileA(m_fname.c_str());
#else
                            remove(m_fname.c_str());
#endif
                            bool suc = StringUtil::SaveFileContent(ptr, totalSize, G2W(m_fname));
							BLOGINFO("[MEMORY][PREDICT]save KeyStat successfully!");
						}
						else{
							BLOGERR("[MEMORY][PREDICT]make md5 for KeyStat failed");
						}
						delete[] ptr;
						return true;
					}
					bool loadContent(Head* phead, PredictMap& predict, int& predictMin)
					{
						if (phead->magic == MagicKeyCapcity)
						{
							if (phead->ksize != sizeof(InverseKey) ||
								phead->isize != sizeof(KeyCapcity) ||
								phead->count != phead->kcount)
								return false;
							int ncount = (phead->fsize - sizeof(Head)) / sizeof(KeyCapcity);
							if (ncount != phead->count)
								return false;
							KeyCapcity* items = (KeyCapcity*)(&phead[1]);
							for (int i = 0; i < ncount;i++)
							{
								predict.emplace(items[i].key, items[i].capcity);
							}
							predictMin = 2;
							return true;
						}
						bool hasError = false;
						int fixedsize = sizeof(Head) + phead->count*sizeof(KeyStatItem);
						int kcount = (phead->fsize - fixedsize) / sizeof(InverseKey);
						if (kcount != phead->kcount ||
							phead->isize != sizeof(KeyStatItem) ||
							phead->ksize != sizeof(InverseKey))
							return false;
						KeyStatItem* items = (KeyStatItem*)(&phead[1]);
						InverseKey* keys = (InverseKey*)((char*)phead + fixedsize);
						for (int i = 0; i < phead->count && !hasError; i++)
						{
							KeyStatItem& item = items[i];
							for (int k = 0; k < item.count; k++)
							{
								int kindex = item.index + k;
								if (kindex < 0 || kindex >= kcount){
									hasError = true; 
									break;
								}
								predict[keys[kindex]] = item.capcity;
							}
						}
						if (!hasError)
							predictMin = InverseSetNew2::ROUND_SIZE;
						return !hasError;
					}
					bool load(PredictMap& predict,int& predictMin,bool& arrayType)
					{
						int fsize = 0;
                        char* ptr = StringUtil::LoadFileContent(G2W(m_fname), fsize);
						if (ptr)
						{
							Head* phead = (Head*)ptr;
							if (phead->fsize == fsize && (phead->magic == Magic||phead->magic==MagicKeyCapcity))
							{
								MD5::tMD5 mdcheck = { 0 };
								if (MD5::FromString(ptr + sizeof(Head), fsize - sizeof(Head), mdcheck, sizeof(mdcheck)) &&
									memcmp(mdcheck, phead->md5, sizeof(mdcheck)) == 0)
								{
									bool suc = loadContent(phead, predict, predictMin);
									arrayType = phead->magic == MagicKeyCapcity;
									delete[] ptr;
									if (!suc)
										predict.clear();
									return suc;
								}
							}
							delete[] ptr;
						}
						return false;
					}
				};
			}
			/////////////////////////////////////////////////////////////////////////
			SpellSearchImpl::KeyCache::~KeyCache(){
				CharInverseKeyMap::iterator it = m_cache.begin();
				for (; it != m_cache.end(); ++it)
				{
					InverseKeySet* v = it.second();
					if (v)delete v;
				}
				m_cache.Clear();
			}
			void SpellSearchImpl::KeyCache::AddKey(const InverseKey& key)
			{
				for (int i = 0; i < internal::kKeyLen; i++)
				{
					InverseKeySet* v = nullptr;
					if (key.code[i] == 0)continue;
					if (m_cache.Find(key.code[i], key.code[i], v) && v)
						v->insert(key);
					else
					{
						v = new InverseKeySet();
						v->insert(key);
						m_cache.Insert(key.code[i], key.code[i], v);
					}
				}
			}
			void SpellSearchImpl::KeyCache::Dump()
			{
				int ncount = 0;
				for (auto it = m_cache.begin(); it != m_cache.end(); ++it)
				{
					ncount+=it.second()->size();
				}
				int hash_bytes = m_cache.Bytes();
				int set_bytes = (ncount + m_cache.Count())*sizeof(InverseKeySet::value_type);
				BLOGINFO("[INDEXER]hash_bytes:%12d  set_bytes:%12d  total:%12d  hashcount:%8d  nodecount:%8d", hash_bytes, set_bytes,
					hash_bytes + set_bytes,m_cache.Count(),ncount);
			}
			SpellSearchImpl::InverseKeySet* SpellSearchImpl::KeyCache::GetKeySet(wchar_t code)
			{
				InverseKeySet* v = nullptr;
				if (m_cache.Find(code, code, v))
					return v;
				return nullptr;
			}
			const SpellSearchImpl::InverseKeySet* SpellSearchImpl::KeyCache::GetKeys(const wstring& text)
			{
				int index = 0;
				InverseKeySet* psets[internal::kKeyLen - 1];
				memset(psets, 0, (internal::kKeyLen - 1)*sizeof(InverseKeySet*));
				for (int i = 0; i < (int)text.size(); i++)
				{
					InverseKeySet* v = nullptr;
					if (!m_cache.Find(text.at(i), text.at(i), v) || nullptr == v)
						continue;
					if (index >= internal::kKeyLen - 1)break;
					psets[index++] = v;
				};
				if (index == 1 && text.size() <= 1)
					return psets[0];
				m_temp.clear();
				for (int i = 0; i < index; i++)
				{
					InverseKeySet* v = psets[i];
					for (InverseKeySet::iterator it = v->begin(); it != v->end(); ++it)
					{
						const InverseKey& key = *it;
						if (wcsstr(key.code,text.c_str())!=nullptr)
							m_temp.insert(*it);
					}
				}
				return &m_temp;
			}
			/////////////////////////////////////////////////////////////////////////
			SpellSearchImpl::SpellSearchImpl(int capcity, int nPageCount, bool verbos) :m_keylen(kKeyLen), m_initialized(false), m_deleteset(true),
                m_indexes(qb::base::GetHashPrimeLargerThan(capcity)),
                m_indexes2(qb::base::GetHashPrimeLargerThan(2048)),
				m_comma(L","), m_max_index(-1), m_max_count2(0),
				m_max_count(0), m_flag_usingset(false), m_flag_searchtag(false),
				m_file(nPageCount), m_flag_verboscheck(verbos),
				m_last_tick(0), m_flag_keycache(false), m_flag_endcode(false),
				m_predict_min(InverseSetNew2::ROUND_SIZE),
				m_predict_mode(kPredictModeArray)
			{
                m_flag_check = false;
                m_flag_usingset = false;
                m_flag_searchtag = false;
                m_flag_verboscheck = false;
                int mode = (kPredictMode)1;
				if (mode<0 || mode > kPredictModeSlot)
				{
					mode = kPredictModeArray;
				}

				m_predict_mode = (kPredictMode)mode;
				HighResTime timer;
				KeyStat stat(m_predict_mode == kPredictModeArray);
				{
					bool arrayType = false;
					bool suc = stat.load(m_predictmap, m_predict_min, arrayType);
					BLOGINFO("[MEMORY][PREDICT]加载债券预估尺寸信息 格式:%s 结果:%s  %dus", 
						arrayType ? "数组" : "插槽",suc ? "成功" : "false", timer.elapsed().microsec());
				}
			}

			SpellSearchImpl::~SpellSearchImpl()
			{

			}

			void SpellSearchImpl::Dump()
			{

				if (1)
				{
					SCOPED_LOCK(m_lock);
					int nbytes = 0;
					IndexListMap::iterator it = m_indexes.begin();
					for (; it != m_indexes.end(); ++it)
					{
						IndexIdRange* iirange = it.second();
						if (iirange == nullptr)continue;
						InverseSet* iset = iirange ? iirange->m_memory_set : nullptr;
						nbytes += sizeof(IndexIdRange);
						if (iset)nbytes += sizeof(InverseSet) + iset->capcity()*sizeof(InverseSet::KeyCount);
					}
					nbytes += m_indexes.size()*sizeof(InverseKey);
					int fbytes = m_file.GetMemoryBytes();
					BLOGINFO("[INDEXER]search engine memory:%12d~=%4.2f  fbytes:%12d~=%4.2f count:%8d-%8d",
						nbytes, nbytes*1.0 / 1024 / 1024, 
						fbytes, fbytes*1.0 / 1024 / 1024,
						m_indexes.size(),  m_indexes.capcity());

					return;
				}



				// 将size最大的前100个打印出来
				// 将max最大的前100个打印出来
				// key最多的前20个为:
				// ANG,111,HAN,NGC,GCD,HCD,行CD,CD0,YIN,NHA,INH,YHC,银行C,ONG,116,SHA,IAN,NGY,ING,001,HAI
				// AND:39306,HAI:11800
#define BVIEW_SIZE(ITEM)	BVIEW("sizeof(%s)\t=\t%d",#ITEM,sizeof(ITEM));
				//BVIEW_SIZE(InverseSet::Base::allocator_type);
				//BVIEW_SIZE(InverseSet::Base::value_type);
				//BVIEW_SIZE(InverseSet::Base::key_type);
				//BVIEW_SIZE(InverseSet::Base::mapped_type);
				//BVIEW_SIZE(InverseSet::Base::pointer);
				struct KeyInfo{
					InverseKey	key;
					int			size;
				};
                std::vector<KeyInfo>	setvec;

				int sum_size = 0;
				int sum_memory = 0;
				int need_memory = 0;
				IndexListMap::iterator it = m_indexes.begin();
				for (; it != m_indexes.end(); ++it)
				{
					KeyInfo ki; ki.key = it.first();
					IndexIdRange* iirange = it.second();
					ki.size = iirange->m_memory_set ? iirange->m_memory_set->size() : iirange->m_length;
					setvec.push_back(ki);
					sum_size += ki.size;
					sum_memory += ki.size*sizeof(InverseSet::Base::value_type);
				}
				need_memory = sum_size*(sizeof(int) + sizeof(char)) + m_indexes.size()*sizeof(InverseKey);
				class ComparatorBySize{
				public:
					bool operator()(const KeyInfo& i1, const KeyInfo& i2)
					{
						return i1.size >= i2.size;
					}
				};


				BVIEW("ComparatorBySize 100,total:%d avgsize:%.2f  mem:%d  memneed:%6d", setvec.size(), sum_size*1.0 / setvec.size(), sum_memory, need_memory);
				std::sort(setvec.begin(), setvec.end(), ComparatorBySize());
				//for (int i = 0; i < 1000; i++)
				//{
				//	KeyInfo& ki = setvec[i];
				//	int nfound = 0;
				//	if (i < 100)
				//	{
				//		CBondContainer& bonds = *CBondContainer::instance();
				//		for (int k = 0; k < bonds.GetSize(); k++)
				//		{
				//			const CBondInfo& bond = bonds.ElementAt(k);
				//			if (IsBondMatch(bond, ki.key.code))
				//				nfound++;
				//		}
				//	}
				//	else
				//		nfound = ki.size;

				//	BVIEW("%3d\t%6s\tsize:%6d\tmax:%6d\tnfound:%6d\t%s", i, W2G(ki.key.code).c_str(), ki.size, 0, nfound,
				//		nfound != ki.size ? "************" : ""
				//		);
				//}
			}


			void SpellSearchImpl::SetFlag(const char* name, bool flag)
			{
				if (name == nullptr)return;
#ifdef WIN32
                if (_stricmp(name, "flag_key_cache") == 0)m_flag_keycache = flag;
                else if (_stricmp(name, "flag_endcode") == 0)m_flag_endcode = flag;
#else
                if (strcasecmp(name, "flag_key_cache") == 0)m_flag_keycache = flag;
                else if (strcasecmp(name, "flag_endcode") == 0)m_flag_endcode = flag;
#endif
			}
			bool SpellSearchImpl::GetFlag(const char* name)const
			{
				if (name == nullptr)return false;
#ifdef WIN32
                if (_stricmp(name, "flag_key_cache") == 0)return m_flag_keycache;
                else if (_stricmp(name, "flag_endcode") == 0)return m_flag_endcode;
#else
                if (strcasecmp(name, "flag_key_cache") == 0)return m_flag_keycache;
                else if (strcasecmp(name, "flag_endcode") == 0)return m_flag_endcode;
#endif
				return false;
			}
			void SpellSearchImpl::BuildIndex(bool diskless)
			{
				if (m_initialized)
					return;
				if (diskless)
				{
					SCOPED_LOCK(m_lock);
					int nshrink = 0;
					for (auto it=m_indexes.begin(); it != m_indexes.end(); ++it)
					{
						IndexIdRange* iirange = it.second();
						InverseSet* iset = iirange ? iirange->m_memory_set : nullptr;
						if (iset && iset->shrink(16))
							nshrink++;
					}
					if (m_flag_keycache)
					{
						HighResTime timer;
						for (auto it = m_indexes.begin(); it != m_indexes.end(); ++it)
						{
							m_keycache.AddKey(it.first());
						}
						for (auto it = m_indexes2.begin(); it != m_indexes2.end(); ++it)
						{
							m_keycache.AddKey(it.first());
						}
						BLOGINFO("[INDEXER]build keycache last %8dus  ", timer.elapsed().microsec());
						if (m_flag_verboscheck)
							m_keycache.Dump();
					}
					SetReady();
					return;
				}
				
				if (UseMappingSet())
				{
					SCOPED_LOCK(m_lock);
					if (m_flag_check)
					{
						IndexListMap::iterator it = m_indexes.begin();
						for (; it != m_indexes.end(); ++it)
						{
							IndexIdRange* iir = it.second();
							BASSERTS(iir->m_memory_set, "");
							iir->m_memory_set->check(m_max_index);
						}
					}
					SetReady();
					return;
				}
				HighResTime timer;
				BS_METRICS("[SPRIT_INIT] IndexIdFile");
				// 将内存的数据写入到映射文件中,然后删除IndexIdRange的m_memory_set对象
				// 只将占用内存过大的写入到映射文件中:超过128个
				struct KeyInfo{
					InverseKey	key;
					IndexIdRange*	ptr;
				};
                std::vector<KeyInfo>	setvec;
				SCOPED_LOCK(m_lock);
				setvec.reserve(m_indexes.size());
				IndexListMap::iterator it = m_indexes.begin();
				for (; it != m_indexes.end(); ++it)
				{
					KeyInfo ki;
					ki.key = it.first();
					ki.ptr = it.second();
					setvec.push_back(ki);
				}
				class ComparatorBySize{
				public:
					bool operator()(const KeyInfo& i1, const KeyInfo& i2)
					{
						return i1.ptr->m_memory_set->size() > i2.ptr->m_memory_set->size();
					}
				};
				std::sort(setvec.begin(), setvec.end(), ComparatorBySize());
				int mem_saved = 0, num_released = 0;
				int mem_saved_cap = 0;
				int bytes = 0;

				// 将内存中的有序数组写入到映射文件中,以节省内存
				MEM_METRIC("BuildIndex delete InverseSet");
				CConvertFast convert;
				bool arrayType = m_predict_mode == kPredictModeArray;
				int itemSize = sizeof(InverseSet::Base::value_type);
				int sumSize = 0, sumCapcity = 0;
				int nset = setvec.size();
				bool useKeyStat = m_predict_mode != kPredictModeNone;
				KeyStat keyStats(arrayType, nset);
				for (int i = 0; i < nset; i++)
				{
					KeyInfo& ki = setvec[i];
					InverseSet* pset = ki.ptr->m_memory_set;
					if (useKeyStat)
						keyStats.add(ki.key, pset->size());
					/*if (ki.ptr->m_memory_set->size() < 16)
						break;*/
					m_file.Update(ki.key, ki.ptr);
					if (m_flag_check)
					{
						IndexIdVec iivec; 
						m_file.GetIndexIdVec(ki.ptr, iivec);
						BASSERT(iivec.count() == pset->size());
						BASSERT(iivec.equal(*pset));
					}

					sumSize += pset->size(); sumCapcity += pset->capcity();
					mem_saved += pset->size()*itemSize + sizeof(InverseSet);
					mem_saved_cap += pset->capcity()*sizeof(InverseSet::Base::value_type) + sizeof(InverseSet);
					num_released++;
					if (m_deleteset)
					{
						ki.ptr->m_memory_set = NULL;
						delete pset;
					}
					//bytes += sizeof(ki.key);
					//bytes += sizeof(IndexIdRange);
				}
				BLOGINFO("[MEMORY][PREDICT]格式:%s %d keys,sumSize:%d sumCapcity:%d usage:%.2f wast:%d last:%dus predict:%d",
					arrayType ? "数组" : "插槽",nset, sumSize, sumCapcity,
					sumSize*100.0 / sumCapcity, (sumCapcity - sumSize)*itemSize,timer.elapsed().microsec(),m_predictmap.size());
				InverseSet::Clear();
				if (useKeyStat)
					keyStats.save();
				m_predictmap.clear();
				int filebytes = m_file.GetMemoryBytes();
				int indexbytes = m_indexes.bytes();
				bytes += filebytes + sizeof(*this);
				bytes += indexbytes - sizeof(IndexListMap);
				BLOGINFO("[SpellSearch][MEMORY][PREDICT]mem_saved:%8d/%8d bytes, num_released:%d num_total:%d/%d  total_memory:%d filebytes:%d indexbytes:%d",
					mem_saved,mem_saved_cap, num_released,m_indexes.size(),m_indexes.capcity(),
					bytes,filebytes,indexbytes);
				BLOGINFO("[SpellSearch][MEMORY][PREDICT]first:%d temp:%d store:%d max_count:%d max_count2:%d last:%8dus",
					m_firstset.size(), m_tempset.size(), m_firststore.count(),
					m_max_count, m_max_count2, timer.elapsed().microsec());
				m_file.Dump();
				if (m_flag_keycache)
				{
					HighResTime timer;
					for (auto it = m_indexes.begin(); it != m_indexes.end(); ++it)
					{
						m_keycache.AddKey(it.first());
					}
					BLOGINFO("[INDEXER]build keycache last %8dus  ", timer.elapsed().microsec());
					//m_keycache.Dump();
				}
            /*	if (m_flag_verboscheck)
				{
					IdLogger::Get().AddGroupLine();
					char buf[1024] = { 0 };
					int len=FMTBUF(buf, "key_count:%8d 2key_count:%6d mem_saved:%8d bytes total_memory:%8d filebytes:%8d indexbytes:%8d max_count:%3d max_index:%6d\n",
						m_indexes.size(), m_indexes2.size(), mem_saved, bytes, filebytes, indexbytes,m_max_count,m_max_index);
					IdLogger::Get().AddBuffer(buf, len);
					IdLogger::Get().Flush();
                }*/
				SetReady();
			}
			void SpellSearchImpl::FindBondsWithLessKey(const wstring& text, Listener* listener)
			{
				if (text.size() <= 0)
				{
					return;
				}				
				const wchar_t* key = text.c_str();
				BaseString keystr = W2G(key, text.size());//之所以不使用m_convert是为了线程考虑
				const char* gkey = keystr.c_str();
				int gkeylen = keystr.size();

				VisitCodeMap visited_codes;
				VisitKeyMap visited_keys;
				bool first_batch = true;
				bool finished = false;
				int nlen = text.size(), scan = 0;
				HighResTime timer;
				for (int k = 0; k < nlen && !finished; k++)//最多2次循环
				{
					InverseKeySet* pset = m_keycache.GetKeySet(text.at(k));
					if (pset == nullptr)continue;
					int index = 0, ncount = pset->size();
					int start = 0;	// 上一次搜索记住的起始索引位置
					bool start_updated = false;		// start已经更新,只需要更新1此
					InverseKeySet::iterator it = pset->begin();
					for (; index < ncount && !finished; ++index, ++it)//遍历每个InverseKey
					{
						if (it == pset->end()){ it = pset->begin(); }
						if (index < start)
							continue;
						const InverseKey& first = *it;
						if (nlen > 1 && wcsstr(first.code, text.c_str()) == nullptr)
							continue;
						if (!visited_keys.Update(first, true))
							continue;
						IndexIdRange* iirange =first.code[kKeyLen-1] == 0 ? m_indexes2.Find(first) : m_indexes.Find(first);
						InverseSet* iset = iirange ? iirange->m_memory_set : nullptr;
						if (iset == nullptr || iset->size() <= 0)
							continue;
						if (first_batch)// 首次:批量 非首次:单个单个处理  批量可能比单个更快
						{
							first_batch = false;
							scan += iset->size();
							if (!listener->OnResult((const int*)iset->GetData(), iset->size(), gkey, gkeylen))
							{
								finished = true;
								break;//终止搜索
							}
							for (int i = 0; i < iset->size(); i++)
								visited_codes.Insert(iset->at(i).getkey(), true);
						}
						else
						{
							int nlast_count = listener->GetResultCount();
							for (int i = 0; i < iset->size(); i++)
							{
								const InverseSet::KeyCount& keycount = iset->at(i);
								if (!visited_codes.Update(keycount.getkey(),true))continue;
								if (!listener->OnResult((const int*)&keycount, 1, gkey, gkeylen))
								{
									finished = true;
									break;//终止搜索
								}
							}
						}
					}
				}
				if (m_flag_verboscheck)
				{
					BLOGINFO("[INDEXER]FindBondsWithLessKey last %8d us  keys_count:%8d  scan:%8d  visited_codes:%4d  visited_keys:%4d",
						timer.elapsed().microsec(), m_indexes.size(), scan, visited_codes.Size(), visited_keys.Size());
				}
			}
			void SpellSearchImpl::FindBondIndexes(const wstring& text, IndexIdVec& first, bool log)
			{
				int pos = 0;
				IndexIdStore* store = UpdateFirstStoreByCheckLastKey(text, pos);
				if (store)
				{
					first.bind(store->first(), store->count(), store->count());
				}
				if (m_flag_verboscheck)
				{
					BLOGDEBUG("[SEARCH_CHECK]UpdateFirstStoreByCheckLastKey text:%s count:%d",
						W2G(text.c_str()).c_str(), store ? store->count() : 0);
                /*	if (log)
					{
						IdLogger::Get().AddStart(text);
                    }*/
				}

				class InverseKeyArray{
					enum{MAX_COUNT=128};//栈上最多支持128个key,即最大长度是130搜索文本长度
					//超出此长度,会使用vector,在堆上分配
					struct InverseKeyInfo{
						InverseKey		key;
						int				count;
					public:
						bool operator<(const InverseKeyInfo& ki)const{
							return count < ki.count;
						}
					};
					InverseKeyInfo			m_stack_array[MAX_COUNT];
					vector<InverseKeyInfo>	m_heap_array;
					int						m_count;
					bool					m_use_heap;
				public:
					InverseKeyArray() :m_use_heap(false), m_count(0){}
					void Add(const InverseKey& k, int count)
					{
						if (!m_use_heap)
						{
							if (m_count < MAX_COUNT)
							{
								InverseKeyInfo& last = m_stack_array[m_count];
								last.key = k;
								last.count = count;
								m_count++;
								return;
							}
							m_heap_array.reserve(MAX_COUNT * 2);
							for (int i = 0; i < m_count; i++)
								m_heap_array.emplace_back(m_stack_array[i]);
							m_use_heap = true;
						}
						if (m_use_heap)
						{
							InverseKeyInfo ki; ki.key = k; ki.count = count;
							m_heap_array.emplace_back(ki);
							m_count = m_heap_array.size();
						}
					}
					void Sort()
					{
						if (m_count <= 1)return;
						if (m_use_heap){
							std::sort(m_heap_array.begin(), m_heap_array.end());
						}
						else{
							std::sort(m_stack_array, m_stack_array + m_count);
						}
					}
					int  GetCount()const{ return m_count; }
					const InverseKey& Get(int index)const{
						return m_use_heap ? m_heap_array[index].key : m_stack_array[index].key;
					}
				};
				InverseKeyArray keys;
				for (int i = pos; !first.empty() && i + m_keylen <= (int)text.size(); i++)
				{
					InverseKey rkey(text.c_str() + i, m_keylen);
					IndexIdRange* iirange = m_indexes.Find(rkey);
					int ncount = iirange ? (iirange->m_memory_set ? iirange->m_memory_set->size():iirange->m_length) : 0;
					if (ncount <= 0)
					{
						first.clear();
						break;
					}
					keys.Add(rkey, ncount);
				}
				if (!m_flag_verboscheck)//快速模式
				{
					if (!first.empty())
					{
						keys.Sort();
						for (int k = 0; k < keys.GetCount(); k++)
						{
							const InverseKey& rkey = keys.Get(k);
							int ncount = 0, before_count = first.count();
							bool suc = IntersectWithKey(first, rkey, k, log, ncount);
							if (!suc)
								break;
						}
					}
				}
				else
				{
					for (int i = pos; !first.empty() && i + m_keylen <= (int)text.size(); i++)
					{
                    //	if (i==pos && store && log)
                    //		WriteIdLog(text.substr(0, pos + m_keylen - 1), first,"result");

						InverseKey rkey(text.c_str() + i, m_keylen);
						int ncount = 0, before_count = first.count();
						bool suc = IntersectWithKey(first, rkey, i, log, ncount);
						if (m_flag_verboscheck)
						{
							char buf[512] = { 0 };
							wstring lastkey = text.substr(0, i + m_keylen - 1);
							FMTBUF(buf, "(%s,%s,%d) %d<==>%d==>%d",
								W2G(lastkey.c_str()).c_str(),
								W2G(wstring(text.c_str() + i, m_keylen).c_str()).c_str(),
								i, before_count, ncount, first.count());
                        /*	if (log)
							{
								std::string type = "result:";
								type += buf;
								WriteIdLog(text.substr(0, i + m_keylen), first, type.c_str());
                            }*/
							BLOGDEBUG("[SEARCH_CHECK]IntersectWithKey%s", buf);
						}
						if (!suc)
							break;
					}
				}
				if ((int)text.size() >= m_keylen)
					m_lastkey = text;
				else
					m_lastkey.clear();
				m_firststore.setcount(first.count());
			}
			namespace{
                bool ContainText(const InverseKey& key, wchar_t c0, wchar_t c1)
				{
					if (key.code[0] == c0)	return c1 == 0 || key.code[1] == c1;
					if (key.code[1] == c0)return c1 == 0 || key.code[2] == c1;
					return key.code[2] == c0 && c1 == 0;
				}
                bool IsSameChar(const wstring& text)
				{
					if ((int)text.size() > 1){
						wchar_t c = text[0];
						for (int i = 1; i < (int)text.size(); i++)
						{
							if (c != text[i])
								return false;
						}
						return true;
					}
					return false;
				}
			}

			void SpellSearchImpl::FindBonds(const wstring& text, Listener* listener)
			{
				/*
					通过输入文本,查询所有可能的索引列表
					特殊模式:当输入文本以"JP:"开头的时候,后续汉字会解析成简拼
							 当输入文本以"QP:"开头的时候,后续汉字会解析成全拼

					// 一下代码是旧实现,性能较低,原因在于:
					//IndexIdStore* store = FindIndexBySpellMatch(text);
					//IndexIdVec first(store);
					//first.transform();
					//listener->OnResult((const int*)first.first(), first.count());
				*/
				class IntHash{
				public:
					size_t operator()(const unsigned int& x) const { return x; }
				};

				IndexIdVec first;
				IndexId	   blanks[2] = { 0, 0 };
				const int keysize = 256;
				const int codesize = 5;
				const wchar_t* code = L"CODE:";
				const wchar_t* keyprefix = L"KEY:"; const int keyprefix_len = 4;
				wchar_t keybuf[keysize] = { 0 };
				const wchar_t* key = text.c_str();
				int len = text.size();
				bool processed = false;
                std::vector<unsigned int> keys;

				SCOPED_LOCK(m_lock);
				if (m_initialized)
				{
					if (!m_flag_searchtag&&!m_flag_verboscheck)
					{
						if (m_flag_keycache && (int)text.size() < m_keylen)
						{
							return FindBondsWithLessKey(text, listener);
						}
						if (text.size() >= 3)
						{
							FindBondIndexes(text, first, m_flag_verboscheck);
						}
						else if (text.size() == 1 || text.size() == 2)
						{
							HighResTime timer;
							int sum = 0;
							wchar_t c = text.at(0);
							wchar_t c1 = text.size() > 1 ? text.at(1) : 0;
                            std::vector<IndexIdRange*> values;
                            std::vector<InverseKey> ikeys;
							auto it = m_indexes.begin(), end = m_indexes.end();
							for (; it != end; ++it)
							{
								const InverseKey& key = it.first();
								if(ContainText(key,c,c1))
								{
									IndexIdRange* iir = it.second();
									sum += iir->m_length;
									values.push_back(iir);
									ikeys.push_back(key);
									if (sum > 256)
										break;
								}
							}

							for (int i = 0; i < (int)values.size(); i++)
							{
								IndexIdRange* iirange = values[i];
								InverseSet* pset = iirange->m_memory_set;
								if (pset)
								{
									for (int i = 0; i < pset->size(); i++)
										keys.push_back(pset->at(i).get());
								}
								else
								{
									IndexIdVec iivec;
									m_file.GetIndexIdVec(iirange, iivec);
									for (int i = 0; i < iivec.size(); i++)
										keys.push_back(iivec.at(i));
								}
							}
							int size = keys.size();
							if (keys.size() > 1)
							{
								std::sort(keys.begin(), keys.end());
								auto last = std::unique(keys.begin(), keys.end());
								size = last - keys.begin();
							}
							m_lastkey.clear();
							if (size>0)
								first.bind(&keys.at(0), size, size);
							BLOGINFO("[SEARCH_CHECK]keys:%6d bonds:%6d last:%8dus", values.size(), keys.size(), timer.elapsed().microsec());
						}
					}
					else{
						if (m_flag_searchtag && len > 3 && wcsncmp(text.c_str(), L"JP:", 3) == 0)
						{
							int quanlen = 0, jianlen = keysize;
							memset(keybuf, 0, keysize * sizeof(wchar_t));
							Spell::Parse(text.c_str() + 3, text.size() - 3, NULL, quanlen, keybuf, jianlen);
							FindBondIndexes(keybuf, first, false);
							key = keybuf; len = jianlen;
						}
						else if (m_flag_searchtag && len > 3 && wcsncmp(text.c_str(), L"QP:", 3) == 0)
						{
							int quanlen = keysize, jianlen = 0;
							memset(keybuf, 0, keysize * sizeof(wchar_t));
							Spell::Parse(text.c_str() + 3, text.size() - 3, keybuf, quanlen, 0, jianlen);
							FindBondIndexes(keybuf, first, false);
							key = keybuf; len = quanlen;
						}
						else if (m_flag_verboscheck && len > codesize && wcsncmp(text.c_str(), code, codesize) == 0)
						{
							memset(keybuf, 0, keysize * sizeof(wchar_t));
							int reallen = text.size() - codesize;
							reallen = reallen >= keysize ? (keysize - 1) : reallen;
                            wcsncpy(keybuf, text.c_str() + codesize, reallen);
							FindBondIndexes(keybuf, first, true);
							key = keybuf; len = reallen;
						}
						else if (m_flag_verboscheck && len > keyprefix_len && wcsncmp(text.c_str(), keyprefix, keyprefix_len) == 0)
						{
							memset(keybuf, 0, keysize * sizeof(wchar_t));
							int reallen = text.size() - keyprefix_len;
							reallen = reallen >= keysize ? (keysize - 1) : reallen;
                            wcsncpy(keybuf, text.c_str() + keyprefix_len, reallen);
							FindBondIndexes(keybuf, first, true);
							key = keybuf; len = reallen;
						}
						else
							FindBondIndexes(text, first, m_flag_verboscheck);
					}
				}
				BaseString keystr = W2G(key, len);//之所以不使用m_convert是为了线程考虑
				const char* gkey = keystr.c_str();
				int gkeylen = keystr.size();
				if (m_flag_endcode && text.size() >= 2)
				{
					m_currentstore.init(m_firststore.first(), m_firststore.count());
					first.bind(m_currentstore.first(), m_currentstore.count(), m_currentstore.count());
					int nsize = text.size(); int ncount = 0;
					InverseKey tail(text.at(nsize - 2), text.at(nsize - 1), 0);
					InverseKey head(0, text.at(0), text.at(1));
					IntersectWithKey(first, tail, 0, false, ncount);
					IntersectWithKey(first, head, 0, false, ncount);
					m_currentstore.setcount(first.count());
					if (listener->OnResult((const int*)first.first(), first.count(), gkey, gkeylen))
					{
						VisitCodeMap visitedmap;
						for (int i = 0; i < first.count(); i++)
							visitedmap.Insert(spell::getkey(first.first()[i]), true);
						first.bind(m_firststore.first(), m_firststore.count(), m_firststore.count());
						for (int i = 0; i < first.count(); i++)
						{
							IndexId id = first.first()[i];
							if (!visitedmap.Update(spell::getkey(id), true))
								continue;
							if (!listener->OnResult((const int*)&id, 1, gkey, gkeylen))
								break;
						}
					}
				}
				else
				{
					if (first.count() <= 0 && first.first() == nullptr)
						first.bind(blanks, 0, 2);
					listener->OnResult((const int*)first.first(), first.count(), gkey, gkeylen);
				}
				return;
			}
			bool SpellSearchImpl::IntersectWithKey(IndexIdVec& first, const InverseKey& rkey, int step, bool log, int& ncount)
			{
				IndexIdRange* iirange = m_indexes.Find(rkey);
				if (iirange == NULL)
				{
					first.clear();
                //	if (log)
                //		WriteIdLog(wstring(rkey.code),first,"3key");
					return false;
				}

				if (iirange->m_memory_set)
				{
					ncount = iirange->m_memory_set->size();
					first.intersect(*iirange->m_memory_set);
                //	if (log)
                //		WriteIdLog(wstring(rkey.code), iirange->m_memory_set, "3key");
					//BVIEW("IndexIdSet[%2d] set key:%s count:%5d result:%5d", step, W2G(rkey.code, 3).c_str(), iirange->m_memory_set->size(), first.count());
				}
				else
				{
					IndexIdVec iivec;
					m_file.GetIndexIdVec(iirange, iivec);
					first.intersect(iivec);
					ncount = iivec.size();
                //	if (log)
                //		WriteIdLog(wstring(rkey.code), iivec, "3key");
					//BVIEW("IndexIdSet[%2d] vec key:%s count:%5d result:%5d", step, W2G(rkey.code, 3).c_str(), iivec.count(), first.count());
				}
				return !first.empty();
			}

			bool SpellSearchImpl::UseMappingSet() const
			{
				return m_flag_usingset;
			}
			bool SpellSearchImpl::AddBondChange(BondChangeBuffer* change)
			{
				if (change == NULL)
					return false;
				const int jian_size = 256;
				const int quan_size = 1024;
				wchar_t jian[jian_size] = { 0 };
				wchar_t jian_now[jian_size] = { 0 };
				wchar_t quan[quan_size] = { 0 };
				wchar_t quan_now[quan_size] = { 0 };

				typedef BondChangeBuffer::ChangeItem Item;
				int ncount = change->GetCount();
				SCOPED_LOCK(m_lock);
				for (int i = 0; i < ncount; i++)
				{
					//const char* old = NULL;
					//const char* now = NULL;
					const Item& item = change->GetChangeItem(i);
					//int id = change->GetChange(i, type, old, now);
					if (item.type == kChangeTypeName)
					{
						if (item.oldlen>0)
						{
							const wchar_t* oldw = m_convert.ToWide(item.old, item.oldlen);
							int oldw_len = m_convert.GetWstrSize();
							int jianlen = jian_size, quanlen = quan_size;
                            qb::base::Spell::Parse(oldw, oldw_len, quan, quanlen, jian, jianlen);
							RemoveIndexForSentence(item.id, oldw, oldw_len, false);
							RemoveIndexForSentence(item.id, jian, jianlen, true);
							RemoveIndexForSentence(item.id, quan, quanlen, true);
						}

						if (item.nowlen>0)
						{
							const wchar_t* noww = m_convert.ToWide(item.now, item.nowlen);
							int noww_len = m_convert.GetWstrSize();
							int jianlen_now = jian_size, quanlen_now = quan_size;
                            qb::base::Spell::Parse(noww, noww_len, quan_now, quanlen_now, jian_now, jianlen_now);
							AddIndexForSentence(item.id, noww, noww_len, false);
							AddIndexForSentence(item.id, jian_now, jianlen_now, true);
							AddIndexForSentence(item.id, quan_now, quanlen_now, true);
						}
					}
					else if (item.type == kChangeTypeNameEn)
					{
						if (item.oldlen > 0)
						{
							const wchar_t* oldw = m_convert.ToWide(item.old, item.oldlen);
							int oldw_len = m_convert.GetWstrSize();
							RemoveIndexForSentence(item.id, oldw, oldw_len, false);
						}

						if (item.nowlen > 0)
						{
							const wchar_t* noww = m_convert.ToWide(item.now, item.nowlen);
							int noww_len = m_convert.GetWstrSize();
							AddIndexForSentence(item.id, noww, noww_len, false);
						}
					}
					else if (item.type == kChangeTypeCode)
					{
						if (item.oldlen > 0)
						{
							const wchar_t* tempkey = m_convert.ToWide(item.old, item.oldlen);
							RemoveIndexForSentence(item.id, tempkey, m_convert.GetWstrSize(), false);
						}

						if (item.nowlen > 0)
						{
							const wchar_t* tempkey = m_convert.ToWide(item.now, item.nowlen);
							AddIndexForSentence(item.id, tempkey, m_convert.GetWstrSize(), false);
						}
						
                    /*	if (m_flag_verboscheck)
						{
							char buf[256] = { 0 };
							int len = FMTBUF(buf, "id:%8d	code:%s\n", item.id, item.now);
							IdLogger::Get().AddIdCode(buf, len);
                        }*/
					}
					else if (item.type == kChangeTypeNameOnly ||
						item.type == kChangeTypePinyin ||
						item.type == kChangeTypePinyinFull)
					{
						bool split = item.type == kChangeTypeNameOnly ? false : true;
						if (item.oldlen > 0)
						{
							const wchar_t* tempkey = m_convert.ToWide(item.old, item.oldlen);
							RemoveIndexForSentence(item.id, tempkey, m_convert.GetWstrSize(), split);
						}
						if (item.nowlen > 0)
						{
							const wchar_t* tempkey = m_convert.ToWide(item.now, item.nowlen);
							AddIndexForSentence(item.id, tempkey, m_convert.GetWstrSize(), split);
						}
					}
				}
				m_lastkey.clear();
				/*BLOGINFO("[DICT][PINYIN]max_index:%d  max_count:%d key_count:%d",
					m_max_index, m_max_count, m_indexes.size()
					);*/
				if (m_flag_check)
				{
					CheckAll();
				}
				return true;
			}
			void SpellSearchImpl::GetAllKeys(vector<wstring>& keys)
			{
				SCOPED_LOCK(m_lock);
				IndexListMap::iterator it = m_indexes.begin();
				for (; it != m_indexes.end(); ++it)
				{
					keys.push_back(it.first().code);
				}
			}
			InverseSet* SpellSearchImpl::FindInverseSet(const InverseKey& key, InverseSet* target)
			{
				IndexIdRange* iirange = m_indexes.Find(key);
				if (iirange == NULL)
					return NULL;
				if (iirange->m_memory_set)
					return iirange->m_memory_set;
				IndexIdVec iivec;
				m_file.GetIndexIdVec(iirange, iivec);
				iivec.copyto(*target);
				return target;
			}

			IndexIdStore* SpellSearchImpl::UpdateFirstStoreByCheckLastKey(const wstring& key, int& pos)
			{
				// 复用上次的结果
				pos = 1;
				if ((int)key.size() < m_keylen)
				{
					if (key.size() >= kReverseKeyLen2)
					{
						pos = key.size();
						return UpdateFirstStoreWithDoubleKey(InverseKey(key.c_str(), key.size()));
					}
					return NULL;
				}

				//
				if (key.size() >= 4 && IsSameChar(key))
					return UpdateFirstStore(InverseKey(key.c_str(), 4));

				if (key.size() >= m_lastkey.size() && 
					(int)m_lastkey.size()>=m_keylen &&
					IsStartWith(key.c_str(), m_lastkey.c_str(), m_lastkey.size())
					)
				{
					pos = m_lastkey.size() - m_keylen + 1;
					return &m_firststore;
				}
				else
				{
					if (key.size() == 4 && InverseKey(key.c_str(), 3) == InverseKey(key.c_str() + 1, 3))
						pos++;
					return UpdateFirstStore(InverseKey(key.c_str(), m_keylen+pos-1));
				}
			}
			IndexIdStore* SpellSearchImpl::UpdateFirstStoreWithDoubleKey(const InverseKey& key)
			{
				IndexIdRange* iirange = m_indexes2.Find(key);
				if (iirange && iirange->m_memory_set)
				{
					m_firststore.init(*iirange->m_memory_set);
					return &m_firststore;
				}
				return NULL;
			}
			IndexIdStore* SpellSearchImpl::UpdateFirstStore(const InverseKey& key)
			{
				IndexIdRange* iirange = m_indexes.Find(key);
				if (iirange == NULL)
					return NULL;
				if (iirange->m_memory_set)
					m_firststore.init(*iirange->m_memory_set);
				else
				{
					IndexIdVec iivec;
					m_file.GetIndexIdVec(iirange, iivec);
					m_firststore.init(iivec.first(), iivec.count());
				}
				return &m_firststore;
			}

			IndexIdStore* SpellSearchImpl::FindIndexBySpellMatch(const wstring& text)
			{
				const wchar_t* name = text.c_str();
				int nlen = text.size();
				if (nlen < m_keylen)
					return NULL;

				SCOPED_LOCK(m_lock);
				InverseSet* first = FindInverseSet(InverseKey(name, m_keylen), &m_firstset);
				for (int i = 1; first && !first->empty() && i + m_keylen <= nlen; i++)
				{
					const InverseSet* pset = FindInverseSet(InverseKey(name + i, m_keylen), &m_tempset);
					if (pset == NULL)
                        return NULL;
					first->intersect(*pset);
				}
				m_firststore.init(*first);
				return &m_firststore;
			}

			void SpellSearchImpl::RemoveIndexForSentence(int index, const wchar_t* sentence, int len,bool split)
			{
				if (len <= 0)
					return;
				strinfo tokens[128] = { 0 };
				int tknum = 0;
				if(split)
					tknum=StringUtil::SplitStringInfo(sentence, len, m_comma, tokens, 128);
				else
				{
					tknum = 1;
					tokens[0].pos = 0;
					tokens[0].len = len;
				}
				for (int i = 0; i < tknum; i++)
				{
					strinfo& token = tokens[i];
					if (token.len < m_keylen)
					{
						if (token.len >= kReverseKeyLen2)
							RemoveIndexForDoubleKey(index, InverseKey(sentence + token.pos, token.len));
						continue;
					}
					
					if (m_flag_endcode)
					{
						RemoveIndexForKey(index, InverseKey(0, sentence[token.pos], sentence[token.pos + 1]));
					}
					int j = 0;
					for (; j + m_keylen <= token.len; j++)
					{
						InverseKey key(sentence + token.pos + j, m_keylen);
						RemoveIndexForKey(index, key);
						if (j > 0)
						{
							InverseKey last(sentence + token.pos + j-1, m_keylen);
							if (key == last)
							{
								last.code[3] = key.code[2];
								RemoveIndexForKey(index,last);
							}
						}
					}
					if (m_flag_endcode && j + m_keylen - 1 == token.len)
						RemoveIndexForKey(index, InverseKey(sentence[token.pos + j], sentence[token.pos + j + 1], 0));

				}
			}

			void SpellSearchImpl::RemoveIndexForKey(int index, const InverseKey& key)
			{
				IndexIdRange* iirange = m_indexes.Find(key);
				if (UseMappingSet())
				{
					if (iirange)
					{
						if (iirange->m_memory_set)
							iirange->m_memory_set->remove(index);
					}
				}
				else
				{
					if (iirange)
					{
						if (iirange->m_memory_set)
							iirange->m_memory_set->remove(index);
						if (iirange->m_bytes > 0)
						{
							m_file.RemoveKey(iirange, index);
						}
					}
				}

				if (m_initialized && m_flag_check)
				{
					CheckIndexForKey(index, key);
				}
			}

			void SpellSearchImpl::AddIndexForSentence(int index, const wchar_t* sentence, int len, bool split)
			{
				if (len <= 0)
					return;
				strinfo tokens[128] = { 0 };
				int tknum = 0;
				if(split)
					tknum=StringUtil::SplitStringInfo(sentence, len, m_comma, tokens, 128);
				else
				{
					tknum = 1;
					tokens[0].pos = 0;
					tokens[0].len = len;
				}
				for (int i = 0; i < tknum; i++)
				{
					strinfo& token = tokens[i];
					if (token.len < m_keylen)
					{
						if (token.len >= kReverseKeyLen2)
						{
							AddIndexForDoubleKey(index, InverseKey(sentence + token.pos, token.len));
							if (IsTinyKeyLogEnable())
							{
								BLOGINFO("[PINYIN][DoubleKey]len:%4d,size:%6d str:%s", token.len,
									m_indexes2.size(),
									W2G(WideString(sentence + token.pos, token.len)).c_str());
							}
						}
						continue;
					}
					
					if (m_flag_endcode)
					{
						AddIndexForKey(index, InverseKey(0,sentence[token.pos], sentence[token.pos+1]));
					}
					int j = 0;
					for (; j + m_keylen <= token.len; j++)
					{
						InverseKey key(sentence + token.pos + j, m_keylen);
						AddIndexForKey(index, key);
						if (j > 0)
						{
							// 额外检查4个字符相同的,也将这种情况增加到表中
							InverseKey last(sentence + token.pos + j - 1, m_keylen);
							if (last == key)
							{
								last.code[3] = key.code[2];
								AddIndexForKey(index, last);
							}
						}
					}
					if (m_flag_endcode && j + m_keylen - 1 == token.len)
						AddIndexForKey(index, InverseKey(sentence[token.pos + j], sentence[token.pos + j + 1], 0));
				}
			}

			void SpellSearchImpl::AddIndexForKey(int index, const InverseKey& key)
			{
				//BASSERTS(wcslen(key.code) == 3, "");
				IndexIdRange* iirange = m_indexes.Find(key);
				if (UseMappingSet())
				{
					// 所有集合数据全部存储在映射文件中,内存占用少,但加载过程慢,此分支不使用
					if (iirange == NULL)
					{
						InverseSet* pset = new InverseSet();
						pset->expand(PredictCount(key));
						pset->add(index);
						m_indexes.Insert(key, pset);
						if (m_initialized)m_keycache.AddKey(key);
					}
					else
					{
						InverseSet* pset = iirange->m_memory_set;
						BASSERTS(pset, "");
						pset->add(index);
						if (m_max_count < pset->getmax())
							m_max_count = pset->getmax();
					}
				}
				else
				{
					/*
						m_bytes 只有在BuildIndex之后才可能>0,表明IndexIdRange的集合已经从
						内存中的InverseSet转移到映射文件中
						一旦转移,以后将不再更新内存中的集合,且内存中的集合肯定是空
					*/
					InverseSet* pset = iirange ? iirange->m_memory_set : NULL;
					int bytes = iirange ? iirange->m_bytes : 0;
					if (bytes > 0)//已经转移
					{
						m_file.AddKey(iirange, index);
					}

					// 以下代码是未转移,使用内存集合,之所以没有使用else,是为了在m_deleteset为false
					// 的情况下,也能保持内存中的m_memory_set,注意,BuildIndex之后,也会有两份
					// 一份在内存中m_memory_set,一份在映射文件中
					if (pset)
					{
						pset->add(index);
						if (m_max_count < pset->getmax())
							m_max_count = pset->getmax();
						if (bytes > 0)
						{
							BASSERTS(iirange->m_length == pset->size(), "");
						}
					}
					else if ((bytes <= 0) || !m_deleteset)
					{
						pset = new InverseSet();
						pset->expand(PredictCount(key));
						pset->add(index);
						m_indexes.Insert(key, pset);
						if (m_initialized)m_keycache.AddKey(key);
					}
				}

				m_max_index = m_max_index < index ? index : m_max_index;
				if (m_initialized && m_flag_check)
					CheckIndexForKey(index, key);
			}
			void SpellSearchImpl::AddIndexForDoubleKey(int index, const InverseKey& key)
			{
				IndexIdRange* iirange = m_indexes2.Find(key);
				InverseSet* pset = iirange ? iirange->m_memory_set : NULL;
				if (pset)
				{
					pset->add(index);
					if (m_max_count2 < pset->getmax())
					{
						m_max_count2 = pset->getmax();
						if (IsTinyKeyLogEnable())
						{
							BLOGINFO("[PINYIN][DoubleKey]max_count2:%6d", m_max_count2);
						}
					}
				}
				else
				{
					pset = new InverseSet();
					pset->expand(PredictCount(key));
					pset->add(index);
					m_indexes2.Insert(key, pset);
				}
			}
			void SpellSearchImpl::RemoveIndexForDoubleKey(int index, const InverseKey& key)
			{
				IndexIdRange* iirange = m_indexes.Find(key);
				if (iirange && iirange->m_memory_set)
				{
					iirange->m_memory_set->remove(index);
				}
			}
			void SpellSearchImpl::CheckAll()
			{
				if (!m_flag_check)
					return;
				IndexListMap::iterator it = m_indexes.begin();
				for (; it != m_indexes.end(); ++it)
				{
					IndexIdRange* iir = it.second();
					InverseSet* pset = iir ? iir->m_memory_set : NULL;
					if (pset)pset->check(m_max_index);
					if (iir->m_bytes>0)
					{
						int last = -1;
						BASSERT(iir->m_offset >= 0 && iir->m_length >= 0);
						if (pset){ BASSERTS(pset->size() == iir->m_length, "%d!=%d", pset->size(), iir->m_length); }
						IndexIdVec iivec;
						m_file.GetIndexIdVec(iir, iivec);
						for (int i = 0; i < iivec.count(); i++)
						{
							int id = spell::getkey(iivec.first()[i]);
							BASSERT(id >= 0 && id <= m_max_index);
							BASSERT(id > last);
							last = id;
						}
					}
				}
			}
			bool SpellSearchImpl::CheckIndexForKey(int index, const InverseKey& key)
			{
				IndexIdRange* iirange = m_indexes.Find(key);
				BASSERT(iirange);
				InverseSet* pset = iirange ? iirange->m_memory_set : NULL;
				if (pset)
				{
					pset->check(m_max_index);
				}
				else
				{
					int last = -1;
					BASSERT(iirange->m_bytes>0 && iirange->m_length >= 0);
					IndexIdVec iivec;
					m_file.GetIndexIdVec(iirange, iivec);
					for (int i = 0; i < iivec.count(); i++)
					{
						int id = spell::getkey(iivec.first()[i]);
						BASSERT(id >= 0 && id <= m_max_index);
						BASSERT(id > last);
						last = id;
					}
				}
				return true;
			}
			int SpellSearchImpl::PredictCount(const InverseKey& key)
			{
				if (m_predictmap.empty())
					return m_predict_min;
				auto it = m_predictmap.find(key);
				if (it != m_predictmap.end())
					return it->second;
				return m_predict_min;
			}
			/////////////////////////////////////////////////////////////////////////
			IndexListMap::IndexListMap(int capcity) :m_hashmap(capcity)
			{

			}
			IndexListMap::~IndexListMap()
			{
				InverseSetPtrHashMap::iterator it = m_hashmap.begin();
				for (; it != m_hashmap.end(); ++it)
				{
					IndexIdRange* iirange = it.second();
					if (iirange->m_memory_set)
						delete iirange->m_memory_set;
					delete iirange;
				}
				m_hashmap.Clear();
			}

			IndexIdRange* IndexListMap::Find(const InverseKey& key)
			{
				IndexIdRange* pset = NULL;
				m_hashmap.Find(key, key.GetHash(), pset);
				return pset;
			}

			void IndexListMap::Insert(const InverseKey& key, InverseSet* isets)
			{
				IndexIdRange* iirange = new IndexIdRange(isets);
				m_hashmap.Insert(key, key.GetHash(), iirange);
			}
			int IndexListMap::bytes()const
			{
				int itemsize = sizeof(InverseKey) + sizeof(IndexIdRange) + 8;
				int bytes = m_hashmap.Bytes();
				int setbytes = 0;
				IndexListMap* cur = const_cast<IndexListMap*>(this);
				for (IndexListMap::iterator it = cur->begin(); it != cur->end(); ++it)
				{
					const IndexIdRange* range = it.second();
					if (range->m_memory_set)
					{
						setbytes += sizeof(InverseSet) + range->m_memory_set->capcity()*sizeof(InverseSetNew2::KeyCount);
					}
				}
				bytes += setbytes;
				return bytes;
			}
		}
	}
}
